Вероятностные алгоритмы проверки чисел на простоту
2025-10-04
Ознакомиться с алгоритмами проверки чисел на простоту. Реализовать их.
Реализовать на языке программирования Julia:
Рисунок 1: Алгоритм, реализующий тест Ферма. Пример отработки
function simvol_Yakobi(n,a)
if n < 3 || a >= n || a < 0
return "\nincorrrect n,a.please try again\n"
end
g = 1
a1 = 0
k = 0
s = 0
while a1 != 1
if 1 == 0
return 0
elseif a == 1
return 1
end
a1 = a
k = 0
while a1 % 2 == 0
k += 1
a1 = round(Int64, a1 / 2)
end
if k % 2 == 0 || (k % 2 == 1 && \\
(n % 8 == 1 || n %8 == 7))
s = 1
elseif k % 2 == 1 && (n % 8 == 3 || n % 8 == 5)
s = -1
end
if a1 == 1
return g*s
end
if n%4==3 && a%4==3
s=-s
end
a = n % a1
n = a1
g *= s
end
endРисунок 2: Алгоритм вычисления числа Якоби. Пример отработки
function test_Soloveya_Shtrassena(n)
if n < 5
return "incorrrect n.please try again"
end
a = rand(2:n-2)
r = powermod(a, round(Int64, (n-1)/2), n)
if r != 1 && r != n-1
return "4islo " * string(n) * " sostavnoe \n"
else
s = simvol_Yakobi(n,a)
if r == s && r != NaN
return "4islo " * string(n) * " sostavnoe \n"
end
return "4islo " * string(n) * ", veroyatno, prostoe\n"
end
endРисунок 3: Алгоритм, реализующий тест Соловея-Штрассена. Пример отработки
function test_Millera_Robina(n)
if n < 5
return "Incorrect input."
end
r = n-1
s = 0
while r % 2 == 0
s += 1
r = round(Int64, r / 2)
end
a = rand(2:n-2)
y = powermod(a, r, n)
if y != 1 && y != n-1
j = 1
while j < s-1 && y != n-1
y = y^2 % n
if y == 1
"4islo " * string(n) * " sostavnoe \n"
end
j += 1
end
if y != n-1
"4islo " * string(n) * " sostavnoe \n"
else
"4islo " * string(n) * ", veroyatno, prostoe\n"
end
else
return "4islo " * string(n) * ", veroyatno, prostoe\n"
end
end Рисунок 4: Алгоритм, реализующий тест Миллера-Рабина. Пример отработки
В ходе лабораторной работы реализованы на языке программирования Julia: